package com.ry.day1129;

import java.util.Arrays;

public class LC563 {

    static class Solution {
        /**
         * @param nums: an integer array and all positive numbers
         * @param target: An integer
         * @return: An integer
         */
        public int backPackV(int[] nums, int target) {
            return shacache(nums,target); //傻缓存
        }

        public int shacache(int[] nums,int target){
            int n= nums.length;
            int[][] dp = new int[n+1][target+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }

            return f1(nums,0,target,dp);
        }

        public int f1(int[] nums,int idx,int rest,int[][] dp){
            if(rest<0) return -1;
            if(idx== nums.length) {
                return rest==0?1:0;
            }
            if(dp[idx][rest] !=-1) return dp[idx][rest];

            int p1 = f1(nums,idx+1,rest,dp);
            int p2 =0;
            int next = f1(nums,idx+1,rest-nums[idx],dp);
            if(next!=-1){
                p2+=next;
            }

            int ans = p1+p2;
            dp[idx][rest] =ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.backPackV(new int[]{1,2,3,3,7},7)); //2
        System.out.println(obj.backPackV(new int[]{1,1,1,1},3)); //4
    }

}
